import java.util.*;

public class leetcode542_01矩阵 {
    public static void main(String[] args) {
        int[][] mat = {{1, 0, 1, 1, 0, 0, 1, 0, 0, 1}, {0, 1, 1, 0, 1, 0, 1, 0, 1, 1}, {0, 0, 1, 0, 1, 0, 0, 1, 0, 0}, {1, 0, 1, 0, 1, 1, 1, 1, 1, 1}, {0, 1, 0, 1, 1, 0, 0, 0, 0, 1}, {0, 0, 1, 0, 1, 1, 1, 0, 1, 0}, {0, 1, 0, 1, 0, 1, 0, 0, 1, 1}, {1, 0, 0, 0, 1, 1, 1, 1, 0, 1}, {1, 1, 1, 1, 1, 1, 1, 0, 1, 0}, {1, 1, 1, 1, 0, 1, 0, 0, 1, 1}};
//        int[][] mat = {{0,0,0}, {0,1,0}, {1,1,1}};
        Solution10 solution10 = new Solution10();
        solution10.updateMatrix(mat);
    }
}


class Solution10 {
    public int[][] updateMatrix(int[][] mat) {
        int n = mat.length, m = mat[0].length;
        int[][] ans = new int[n][m];
        Queue<int[]> queue = new LinkedList<>();
//        Arrays.stream(mat).forEach(p -> System.out.println(Arrays.toString(p)));
//        Arrays.stream(ans).forEach(p -> System.out.println(Arrays.toString(p)));

        // 找出首轮与0相邻的1，放入队列
        for (int i = 0; i < n; i++) {
            for (int k = 0; k < m; k++) {
                if (mat[i][k] == 0) {
                    int[][] dirs = {{i - 1, k}, {i + 1, k}, {i, k - 1}, {i, k + 1}};
                    for (int[] dir : dirs) {
                        int r = dir[0], c = dir[1];
                        if (r >= 0 && r < n && c >= 0 && c < m && mat[r][c] == 1 && ans[r][c] == 0) {
                            queue.offer(dir);
                            // 与0相邻的1距离必定为1
                            ans[r][c] = 1;
                        }
                    }
                }
            }
        }
        while (!queue.isEmpty()) {
            int[] ik = queue.poll();
            int i = ik[0], k = ik[1];
            int[][] dirs = {{i - 1, k}, {i + 1, k}, {i, k - 1}, {i, k + 1}};
            for (int[] dir : dirs) {
                int newR = dir[0], newC = dir[1];
                if (newR >= 0 && newC >= 0 && newR < n && newC < m && mat[newR][newC] == 1 && ans[newR][newC] == 0) {

                    // 下一轮队列遍历的距离值为上一轮的距离值+1
                    queue.offer(dir);
                    ans[newR][newC] = ans[i][k] + 1;
                }
            }
        }
        return ans;
    }

    private int calc_dist(int[] rc1, int[] rc2) {
        return Math.abs(rc2[1] - rc1[1]) + Math.abs(rc2[0] - rc1[0]);
    }
}